#include<iostream>
#include<vector>
using namespace std;
/*
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
解题思路：
该题与前一道组合总和的题目类似，差别在于没有明确给出递归深度以及数可以重复利用
递归深度的条件可以有sum>target以及sum==target来进行判断
在每一层遍历的时候同样若当前层的第一个节点为1，则第二个节点在遍历的时候就不能再取1了，这样做是为了防止取1的节点往下递归造成
与第二个节点产生重复
*/

//全局变量
vector<vector<int>> result;
vector<int> path;
void trackbacking(vector<int> candidates,int target,int sum,int index)
{
    //递归终止条件
    if(sum>target)
        return;
    else if(sum==target)
    {
        result.push_back(path);
        return;
    }
    for(int i=index;i<candidates.size();i++)
    {
        sum+=candidates[i];
        path.push_back(candidates[i]);
        //此时由于可以重复利用元素，所以递归的开始下标应该从递归的当前元素开始
        trackbacking(candidates,target,sum,i);
        //回溯
        sum-=candidates[i];
        path.pop_back();
    }
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        trackbacking(candidates,target,0,0);
        return result;
}
int main()
{
    cout<<"enter a target:"<<endl;
    int target;
    cin>>target;
    cout<<"enter a number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter candidates:"<<endl;
    vector<int> candidates(number);
    for(int i=0;i<number;i++)
        cin>>candidates[i];
    vector<vector<int>> result = combinationSum(candidates,target);
    for(int i=0;i<result.size();i++)
    {
        for(int j=0;j<result[i].size();j++)
        {
            cout<<result[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}